20220320-TIL

오늘 알고리즘 문제는 간선들의 비용이 균등하게 바뀌는 상황에서 최단 경로를 찾는 문제였다.

• 세금 문제는 최단 경로를 구성하는 데 필요한 간선 수와 거리를 기록해두는 식으로 풀었다.
• 풀이 방향성은 맞았는데 구현 과정에서 최적화를 제대로 못 해서 시간 초과 판정을 받았다;
  (모든 정점에 대해, 가능한 모든 간선 수에 대해 누적 거리를 확인 -> 불필요한 계산이 발생함;)
• 더 적은 간선으로 최단 경로를 구성할 수 있는 경우엔 탐색을 멈추도록 개선해서 해결했다.
  (질문 게시판에도 도움 되는 글이 별로 없어서 구글에 검색함 -> 아이디어만 맞아서 아쉬웠음..)
• 모든 경로에 대한 최단 거리를 구하는 동적 계획법 풀이도 있었다. (코드 보고 놀랐음 ㅋㅋ)